package com.practice.niuke.new_direct_practice.class19;

/**
 * 给定一棵二叉树的头节点head， 可以从树中的任何一点出发， 如果走的话只能向下， 也可以
 * 选择随时停止， 所形成的轨迹叫做一条路径， 路径上所有值的累加和叫作路径和。 求这棵树
 * 上的最大路径和。
 */
public class Code01_MaxDistanceInTree {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    public static class Info {
        /**
         * 从头节点出发的最大路径和
         */
        public int fromHeadMaxPathSum;
        /**
         * 整棵树的最大路径和
         */
        public int allMaxPathSum;

        public Info(int fromHeadMaxPathSum, int allMaxPathSum) {
            this.fromHeadMaxPathSum = fromHeadMaxPathSum;
            this.allMaxPathSum = allMaxPathSum;
        }
    }

    /**
     * 递归函数
     *
     * @param x 以x节点为头
     * @return Info
     */
    public static Info process(Node x) {
        if (x == null) {
            return null;
        }
        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);
        // 可能性1：与x有关但是x不往下走了
        int p1 = x.value;
        // 可能性2：与x有关，x决定往左走
        int p2 = x.value + (leftInfo == null ? 0 : leftInfo.fromHeadMaxPathSum);
        // 可能性3：与x有关，x决定往右走
        int p3 = x.value + (rightInfo == null ? 0 : rightInfo.fromHeadMaxPathSum);

        // 必须以x出发的最大路径和，可能性1、可能性2、可能性3的最大值
        int fromHeadMaxPathSum = Math.max(p3, Math.max(p1, p2));
        // 以x为头的树，整棵树的最大路径和
        int allMaxPathSum = fromHeadMaxPathSum;
        // 可能性4：与x无关，为左树上的整棵树的最大路径和
        if (leftInfo != null) {
            allMaxPathSum = Math.max(allMaxPathSum, leftInfo.allMaxPathSum);
        }
        // 可能性5：与x无关，为右树上的整棵树的最大路径和
        if (rightInfo != null) {
            allMaxPathSum = Math.max(allMaxPathSum, rightInfo.allMaxPathSum);
        }
        return new Info(fromHeadMaxPathSum, allMaxPathSum);
    }

    /**
     * 求整棵树的最大路径和（调用递归函数的主函数）
     *
     * @param head 头节点
     * @return int
     */
    public static int maxPathSum(Node head) {
        return process(head).allMaxPathSum;
    }

    /**
     * 新的路径定义：从二叉树的任意一个节点到任意一个节点都是路径，
     * 节点的个数为路径的长度（除了节点自己到自己的情况，每个节点只能经过一次）。
     * 求最大路径长度
     */

    public static int maxPathLen(Node head){
        return func(head).maxPathLen;
    }

    public static class Data{
        public int height;
        public int maxPathLen;

        public Data(int height, int maxPathLen) {
            this.height = height;
            this.maxPathLen = maxPathLen;
        }
    }

    public static Data func(Node x){
        if (x == null){
            return null;
        }
        Data leftData = func(x.left);
        Data rightData = func(x.right);

        int height = 1 + Math.max((leftData == null ? 0: leftData.height), (rightData == null? 0: rightData.height));
        int maxPathLen = 1 + (leftData == null ? 0: leftData.height) + (rightData == null? 0: rightData.height);
        if (leftData!=null){
            maxPathLen = Math.max(maxPathLen, leftData.maxPathLen);
        }
        if (rightData != null){
            maxPathLen = Math.max(maxPathLen, rightData.maxPathLen);
        }
        return new Data(height, maxPathLen);
    }

    public static void main(String[] args) {
        Node head1 = new Node(1);
        head1.left = new Node(2);
        head1.right = new Node(3);
        head1.left.left = new Node(4);
        head1.left.right = new Node(5);
        head1.right.left = new Node(6);
        head1.right.right = new Node(7);
        head1.left.left.left = new Node(8);
        head1.right.left.right = new Node(9);
        System.out.println(maxPathSum(head1));

        Node head2 = new Node(1);
        head2.left = new Node(2);
        head2.right = new Node(3);
        head2.right.left = new Node(4);
        head2.right.right = new Node(5);
        head2.right.left.left = new Node(6);
        head2.right.right.right = new Node(7);
        head2.right.left.left.left = new Node(8);
        head2.right.right.right.right = new Node(9);
        System.out.println(maxPathSum(head2));
    }
}
